/*Projeto - Programacao Concorrente

Marcos Tamegushi
William Matsui
Yuri Machioni

Compilacao: mpicc main.c -o main
Execucao(recomendado):   mpirun -np 4 main 45 1 119 > out

Os parametros sao respectivamente: o tamanho inicial da mensagem trocada entre os nós,
o tamanho minimo e o tamanho inicial da fase de geracao de subpalavras.

Recomenda-se redirecionar a saida para um arquivo para que apenas as mensagens do programa
sejam exibidos na tela e as palavras geradas nao atrapalhem.
*/

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>
#include <time.h>
#include <mpi.h>

#define INC 100 //incremento dos vetores de palavras. cada vez que se tenta inserir uma palavra num vetor cheio, ele aloca mais INC palavras
#define TAMANHO_MAX 100 //tamanho maximo de uma palavra

typedef struct {
    char* string;
    char found;
} palavra;

/*exemplo de matriz de palavras:

x(0)   b(0)   g(0)   d(0)   w(0) ...
pe(0)  oi(0)  no(0)  vi(0)  ze(0) ...
lua(0) sol(0) pre(0) pau(0) ret(0) ...
.        .
.        .
.        .
(o 0 quer dizer que nao foi encontrada ainda)
*/

void check(void* ptr, char* errorMSG); //checa se ptr eh NULL e imprime errorMSG se for
int comparator(const void *elem1, const void *elem2); //comparador de strings contidas em palavras, para ser usado pelo qsort e bsearch
palavra** split(char* buffer, int* contador, int tamanhoMaximo); //quebra uma string e retorna suas substrings numa matriz de palavras
palavra** discard(palavra** original, int* contadorVelho, int* contadorNovo, int tamanhoMaximo); //retorna outra matriz sem elementos repetidos. requer que a original esteja ordenada
char* fileToBuffer(char* filename); //le um arquivo e o retorna numa string
char* dividePalavras(palavra** matriz, int altura, int* larguras); //quebra palavras com comprimento maior que 5 em subpalavras
void imprimeMatriz(palavra** matriz, int altura, int* larguras);
void limpaMatriz(palavra** matriz, int altura, int* larguras);
void randomizeWord(char* word, int size); //randomiza os caracteres de word (valores entre a e z mais o hifen)

int main(int argc, char *argv[])
{
    palavra **matrizSuja, **matriz; /*matriz com repeticoes e sem repeticoes*/
    palavra **submatrizSuja, **submatriz; /*matriz com subpalavras*/
    char *bigBuffer, *subBigBuffer; /*string contendo o arquivo inteiro e string contendo as subpalavras separadas por virgulas*/
    int i, j, k;
    int contadorVelho[TAMANHO_MAX]; /*contador de palavras de tamanho i da matriz suja*/
    int contadorNovo[TAMANHO_MAX]; /*contador de palavras de tamanho i da matriz limpa*/
    int contadorSubVelho[TAMANHO_MAX]; /*contador de subpalavars de tamanho i na submatriz suja*/
    int contadorSubNovo[TAMANHO_MAX]; /*contador de subpalavars de tamanho i na submatriz suja*/
    int totalPalavras = 0, totalSemRepeticao = 0;
    float comprimentoMedioT = 0.0, comprimentoMedioS = 0.0; /*comprimento medio das palavras com e sem repeticoes*/
    int found[TAMANHO_MAX], foundTotal = 0; /*vetor com numero de palavras de tamanho i ja encontradas, total de palavras ja encontradas*/
    int subFound[TAMANHO_MAX], subFoundTotal = 0; /*analogo para subpalavras*/
    palavra temp;
    int index; /*posicao da palavra encontrada por bsearch*/
    int printCount = 0; /*para calculo da porcentagem*/
    int time1, time2, time3; /*para calculo do tempo*/
    int quantidadeMinima; /*quantidade minima de palavras que cada processo tem que encontrar antes de informar os demais*/
    int QTD_MIN; /*valor minimo que essa quantidade pode atingir (ela varia com o numero de palavras ja encontradas)*/
    int SUB_QTD_TRANSMISSAO; /*analogo a quantidadeMinima, porem se aplica na busca por subpalavras*/

    /*variaveis do MPI*/
    int myrank, nprocs; /*rank deste processo, numero de processos*/
    int *recvcounts, *rdispls, *sendcounts, *sdispls; /*vetores para passagem de mensagens*/
    int *foundIndexes, *receivedIndexes; /*indices das palavras de tamanho i que este processo encontrou, vetor armazenar os indices que os outros processos encontraram*/

    if(argc != 4) {
        fprintf(stderr, "Argumentos da linha de comando incorretos. Usando valores padrao: 45 1 119\n");
        quantidadeMinima = 45;
        QTD_MIN = 1;
        SUB_QTD_TRANSMISSAO = 119;

    } else {
        sscanf(argv[1],"%d",&quantidadeMinima);
        sscanf(argv[2],"%d",&QTD_MIN);
        sscanf(argv[3],"%d",&SUB_QTD_TRANSMISSAO);
    }

    MPI_Init(&argc, &argv);                 //inicializa MPI
    MPI_Comm_rank(MPI_COMM_WORLD, &myrank); //pega o rank deste processo
    MPI_Comm_size(MPI_COMM_WORLD, &nprocs); //numero total de processos

    foundIndexes = calloc(SUB_QTD_TRANSMISSAO, sizeof(int));
    receivedIndexes = calloc(nprocs * SUB_QTD_TRANSMISSAO, sizeof(int));

    recvcounts = (int*) malloc (nprocs * sizeof(int));  //alocacao de vetor de quantidades
    rdispls =    (int*) malloc (nprocs * sizeof(int));     //alocacao de vetor de offsets
    sendcounts = (int*) malloc (nprocs * sizeof(int));  //alocacao de vetor de quantidades
    sdispls =    (int*) malloc (nprocs * sizeof(int));     //alocacao de vetor de offsets

    check(recvcounts, "Erro na alocacao de vetores de comunicacao");
    check(rdispls, "Erro na alocacao de vetores de comunicacao");
    check(sendcounts, "Erro na alocacao de vetores de comunicacao");
    check(sdispls, "Erro na alocacao de vetores de comunicacao");

    for(i = 0; i < nprocs ; i++){
        recvcounts[i] = quantidadeMinima;    //seta quantidades a serem lidas de cada no quando MPI_alltoallv() for chamado
        rdispls[i] = i * quantidadeMinima; //seta offset a partir do qual escrever quando MPI_alltoallv() for chamado
        sendcounts[i] = quantidadeMinima;    //seta quantidades a serem enviadas a cada no
        sdispls[i] = 0; //seta offset do endereco inicial a ser enviado ao no de rank i
    }

    temp.string = (char*) malloc((TAMANHO_MAX+1) * sizeof(char));

    srand(time(NULL) / (myrank+1)); /*semea gerador de numeros aleatorios com o tempo atual*/

    if(myrank == 0) fprintf(stderr, "\nLendo arquivo...\n");
    bigBuffer = fileToBuffer("palavras.txt"); /*le o arquivo para a string*/

    matrizSuja = split(bigBuffer, contadorVelho, TAMANHO_MAX); /*faz a insercao das palavras na matriz*/
    free(bigBuffer); /*libera o buffer*/

    if(myrank == 0)fprintf(stderr, "Ordenando...\n");
    for(i = 1; i < TAMANHO_MAX; i++){
        qsort(matrizSuja[i], contadorVelho[i], sizeof(palavra), comparator); /*ordena matriz suja*/
        found[i] = 0; /*zera o numero de encontrados*/
    }

    if(myrank == 0)fprintf(stderr, "Eliminando repeticoes...\n");
    matriz = discard(matrizSuja, contadorVelho, contadorNovo, TAMANHO_MAX); /*gera uma matriz sem repeticoes a partir da suja ordenada*/
    limpaMatriz(matrizSuja, TAMANHO_MAX, contadorVelho); /*libera a matriz com repeticoes*/

    for(i = 1; i < TAMANHO_MAX; i++){  /*conta as palavras das matrizes e faz calculo o comprimento medio*/
        totalPalavras += contadorVelho[i];
        totalSemRepeticao += contadorNovo[i];
        comprimentoMedioS += i*contadorNovo[i];
        comprimentoMedioT += i*contadorVelho[i];
    }
    comprimentoMedioS /= (float) totalSemRepeticao;
    comprimentoMedioT /= (float) totalPalavras;

    if(myrank == 0){
        fprintf(stderr, "-> Total de palavras: %d, Comprimento medio com repeticoes: %f\n", totalPalavras, comprimentoMedioT);
        fprintf(stderr, "-> Total sem repeticoes: %d, Comprimento medio sem repeticoes: %f\n", totalSemRepeticao, comprimentoMedioS);
        time1 = clock();
    }
    //imprimeMatriz(matriz, TAMANHO_MAX, contadorNovo);

    //cria palavra randomicamente e procura em cada vetor com bsearch
    totalSemRepeticao = 0;
    for(i = 1; i < 6; i++)
        totalSemRepeticao += contadorNovo[i];

    if(myrank == 0) fprintf(stderr, "\nGerando palavras <= 5...\n");
    i = 1;
    k = 0;
    while(i <= 5){ /*gera palavras entre 1 e 5*/
        while(found[i] < contadorNovo[i]) /*enquanto nao encontrou todas com tamanho i*/
        {
            palavra* ptr; /*ponteiro para apontar para a palavra encontrada*/

            randomizeWord(temp.string, i); /*randomiza a string a ser usada como chave de busca*/
            ptr = bsearch(&temp, matriz[i], contadorNovo[i], sizeof(palavra), comparator); /*busca na linha da matriz que tem palavras de tamanho i*/
            index = (ptr - matriz[i]); /*determina o indice da palavra encontrada com base em seu ponteiro*/
            if(ptr != NULL && !matriz[i][index].found){ /*se encontrou e nao tinha encontrado antes*/
                matriz[i][index].found = 1; /*seta flag de encontrado*/
                found[i]++; /*incrementa contador de encontrados de tamanho i*/

                if(i == 5){
                    foundIndexes[k] = index; /*adiciona indices das palavras encontradas no vetor a ser enviado*/
                    k++;
                }

                if(myrank == 0){ /*no mestre calcula porcentagem e tempo e imprime na tela*/
                    printf("%s found\n", temp.string);

                    for(j=0;j<9;j++) {
                        if((100*(foundTotal + found[i]))/totalSemRepeticao > 10*(j+1) && printCount == j){
                            printCount++;
                            time2 = clock();
                            time3 = (time2 - time1)/CLOCKS_PER_SEC;
                            fprintf(stderr,"Encontradas %.2lf%% das palavras <= 5 (%d segundos) | Trocando informacoes a cada %d acertos\n",
                                     (double)(foundTotal + found[i]) * 100.0 /(double) totalSemRepeticao, time3, quantidadeMinima);
                        }
                    }
                }

            }
            if(k == quantidadeMinima && i == 5){ /*se ja encontrou palavras suficientes para transmitir*/
                MPI_Alltoallv(foundIndexes, sendcounts, sdispls, MPI_INT, receivedIndexes, recvcounts, rdispls, MPI_INT, MPI_COMM_WORLD); /*envia de todos para todos*/

                for(k = 0; k < quantidadeMinima * nprocs; k++){ /*marca como encontrado as palavras encontradas por outros nos*/
                    if(matriz[i][receivedIndexes[k]].found == 0){
                        found[i]++;
                        matriz[i][receivedIndexes[k]].found = 1;
                        if(myrank == 0){
                            printf("%s found by other node\n", matriz[i][receivedIndexes[k]].string); /*no mestre informa quando outro no encontrou a palavra*/
                        }
                    }
                }
                if(quantidadeMinima > QTD_MIN){ /*decrementa a quantidade de acertos necessarios para trocar mensagens*/
                    quantidadeMinima--;
                    for(k = 0; k < nprocs; k++){
                        sendcounts[k] = quantidadeMinima;
                        recvcounts[k] = quantidadeMinima;
                        rdispls[k] = quantidadeMinima * k;
                    }
                }
                k = 0;
            }
        }
        foundTotal += found[i];

        i++; /*incrementa tamanho da palavra a ser gerada e buscada*/
    }
    if(myrank == 0){
        time2 = clock();
        time3 = (time2 - time1)/CLOCKS_PER_SEC;
        fprintf(stderr,"Encontradas 100%% das palavras <= 5 (%d segundos)\n", time3);
    }

    /*repeticao do processo de filtragem dos dados, desta vez a entrada nao eh o arquivo mas sim um vetor
    (subBigBuffer) contendo as palavras maiores que 5 quebradas a cada 5 caracteres e separadas por virgulas.
    assim reaproveitamos as funcoes split e discard para inserir os fragmentos numa matriz semelhante a primeira
    a partir desta matriz.
    */

    if(myrank == 0) fprintf(stderr, "\nRepartindo palavras > 5...\n");
    subBigBuffer = dividePalavras(matriz, TAMANHO_MAX, contadorNovo);

    submatrizSuja = split(subBigBuffer, contadorSubVelho, 6); /*faz a insercao das subpalavras na matriz*/

    free(subBigBuffer); /*libera o buffer*/

    if(myrank == 0) fprintf(stderr, "Ordenando...\n");
    totalSemRepeticao = 0;
    for(i = 1; i < 6; i++){
        qsort(submatrizSuja[i], contadorSubVelho[i], sizeof(palavra), comparator); /*ordena matriz suja*/
        subFound[i] = 0; /*zera o numero de encontrados*/
    }

    if(myrank == 0) fprintf(stderr, "Eliminando repeticoes\n");
    submatriz = discard(submatrizSuja, contadorSubVelho, contadorSubNovo, 6); /*gera uma matriz de subpalavras sem repeticoes a partir da suja ordenada*/
    limpaMatriz(submatrizSuja, 6, contadorSubVelho); /*libera a submatriz com repeticoes*/

    for(i = 1; i < 6; i++)
        totalSemRepeticao += contadorSubNovo[i];

    quantidadeMinima = SUB_QTD_TRANSMISSAO;
    k = 0;
    i = 1;
    for(i = 0; i < nprocs ; i++){ /*volta o tamanho dos blocos de transmissao ao normal*/
        recvcounts[i] = quantidadeMinima;
        rdispls[i] = i * quantidadeMinima;
        sendcounts[i] = quantidadeMinima;
        sdispls[i] = 0;
    }

    if(myrank == 0) fprintf(stderr, "\nGerando subpalavras...\n");

    printCount = 0;
    while(i <= 5){ /*gera subpalavras entre 1 e 5*/
        while(subFound[i] < contadorSubNovo[i]) /*enquanto nao encontrou todas com tamanho i*/
        {
            palavra* ptr; /*ponteiro para apontar para a palavra encontrada*/
            randomizeWord(temp.string, i); /*randomiza a string a ser usada como chave de busca*/
            ptr = bsearch(&temp, submatriz[i], contadorSubNovo[i], sizeof(palavra), comparator); /*busca na linha da matriz que tem palavras de tamanho i*/
            index = (ptr - submatriz[i]); /*determina o indice da palavra encontrada com base em seu ponteiro*/
            if(ptr != NULL && !submatriz[i][index].found){ /*se encontrou e nao tinha encontrado antes*/
                submatriz[i][index].found = 1; /*seta flag de encontrado*/
                subFound[i]++; /*incrementa contador de encontrados de tamanho i*/

                if(i == 5){
                    foundIndexes[k] = index; /*adiciona indices das palavras encontradas no vetor a ser enviado*/
                    k++;
                }

                if(myrank == 0){ /*no mestr calcula porcentagem e tempo e imprime*/
                    printf("%s found\n", temp.string);

                    for(j=0;j<9;j++) {
                        if((100*(subFoundTotal + subFound[i]))/totalSemRepeticao > 10*(j+1) && printCount == j){
                            printCount++;time2 = clock();
                            time3 = (time2 - time1)/CLOCKS_PER_SEC;
                            fprintf(stderr,"Encontradas %.2lf%% das palavras <= 5 (%d segundos) | Trocando informacoes a cada %d acertos\n",
                                     (double)(subFoundTotal + subFound[i]) * 100.0 /(double) totalSemRepeticao, time3, quantidadeMinima);
                        }
                    }
                }
            }
            if(k == quantidadeMinima && i == 5){ /*se ja encontrou palavras suficientes para transmitir*/

                MPI_Alltoallv(foundIndexes, sendcounts, sdispls, MPI_INT, receivedIndexes, recvcounts, rdispls, MPI_INT, MPI_COMM_WORLD); /*envia de todos para todos*/

                for(k = 0; k < quantidadeMinima * nprocs; k++){
                    if(submatriz[i][receivedIndexes[k]].found == 0){
                        subFound[i]++;
                        submatriz[i][receivedIndexes[k]].found = 1;
                        if(myrank == 0){
                            printf("%s found by other node\n", submatriz[i][receivedIndexes[k]].string);
                        }
                    }
                }
                if(quantidadeMinima > QTD_MIN){
                    quantidadeMinima--;
                    for(k = 0; k < nprocs; k++){
                        sendcounts[k] = quantidadeMinima;
                        recvcounts[k] = quantidadeMinima;
                        rdispls[k] = quantidadeMinima * k;
                    }
                }
                k = 0;
            }

        }
        subFoundTotal += subFound[i];
        i++; /*incrementa tamanho da palavra a ser gerada e buscada*/
    }
    if(myrank == 0){
        time2 = clock();
        time3 = (time2 - time1)/CLOCKS_PER_SEC;
        fprintf(stderr,"Encontradas 100%% das subpalavras <= 5 (%d segundos)\n", time3);
        fprintf(stderr, "\nLimpando...\n");
    }

    free(temp.string); /*limpa a caca*/
    free(rdispls);
    free(sdispls);
    free(recvcounts);
    free(sendcounts);
    free(foundIndexes);
    free(receivedIndexes);
    limpaMatriz(matriz, TAMANHO_MAX, contadorNovo); /*limpa a matriz sem repeticoes*/
    limpaMatriz(submatriz, 6, contadorSubNovo);
    MPI_Finalize();

    return 0;
}

/*funcao para checar se um ponteiro eh nulo e imprimir mensagem de erro*/
void check(void* ptr, char* errorMSG){
    if(ptr == NULL){
        printf("%s", errorMSG);
        exit(-1);
    }
}

int comparator(const void *elem1, const void *elem2) /*compara strings para ser usado pelo quicksort e bsearch*/
{
    palavra* string1 = (palavra*) elem1;
    palavra* string2 = (palavra*) elem2;
    return strcmp(string1->string, string2->string);
}

/*quebra a string em uma matriz de palavras, em que uma palavra na linha k tem tamanho k.
o contador passado por referencia retorna o numero de palavras com cada comprimento
(contador[m] = numero de palavras com comprimento m (e portanto na linha m))
o contador deve ser passado inicializado com tamanhoMaximo posicoes ja alocadas.
*/

palavra** split(char* buffer, int* contador, int tamanhoMaximo){
    int i;
    char* temp;
    int tamanhoTemp;
    int *tamanhoAtual; //espaco alocado para o vetor de palavras matriz[i];
    palavra** matriz;

    matriz = (palavra**) malloc(tamanhoMaximo * sizeof (palavra*)); //aloca a matriz de palavras
    check(matriz, "Erro ao alocar matriz de palavras(1).\n");

    for(i = 0; i < tamanhoMaximo; i++){ //inicializa cada vetor de palavras apontando pra NULL
        matriz[i] = NULL;
        contador[i] = 0;
    }

    tamanhoAtual = (int*) calloc(tamanhoMaximo, sizeof(int));

    temp = strtok(buffer, ",");

    do{
        tamanhoTemp = strlen(temp); //fixa o tamanho da palavra atual para esta iteracao, evita chamadas a strlen.

        if(strstr(temp, " ") == NULL){ // se nao tem espaco na string
            if(tamanhoTemp > tamanhoMaximo){
                printf("ha uma palavra maior do que o programa suporta.\n");
                exit(-1);
            }

            if(contador[tamanhoTemp] >= tamanhoAtual[tamanhoTemp]){ //se nao cabe mais palavras de tamanho tamanhoTemp no vetor de palavras deste tamanho.
                tamanhoAtual[tamanhoTemp] += INC;
                matriz[tamanhoTemp] = realloc(matriz[tamanhoTemp], tamanhoAtual[tamanhoTemp] * sizeof(palavra)); //aloca espaco para mais 100 palavras de tamanho tamanhoTemp.
                check(matriz[tamanhoTemp], "Erro ao alocar matriz de palavras(2).\n");
                for(i = tamanhoAtual[tamanhoTemp] - INC; i < tamanhoAtual[tamanhoTemp]; i++){ //aloca espaco para as palavras de fato.
                    matriz[tamanhoTemp][i].string = (char*) malloc ((tamanhoTemp+1) * sizeof(char)); //aloca espaco para as palavras + o \0
                    check(matriz[tamanhoTemp][i].string, "Erro ao alocar matriz de palavras(3).\n");
                }
            }

            //lower(temp);
            strcpy( matriz[tamanhoTemp][contador[tamanhoTemp]].string, temp); //copia a palavra para a matriz
            matriz[tamanhoTemp][contador[tamanhoTemp]].found = 0; //seta flag de nao encontrada

            contador[tamanhoTemp]++;  //incrementa o contador de palavras com tamanho tamanhoTemp
        }
        temp = strtok(NULL, ","); //pega a proxima palavra.
    } while(temp != NULL);

    free(tamanhoAtual);
    return matriz;
}

/*eh muito mais eficiente ler todas as palavras para a matriz (O(n)), ordena-las (O(nlog(n) caso medio) e depois descartar
as repetidas (O(n)) do que fazer a leitura sem repeticoes (O(n^2) caso medio) pelo menos para esse numero de palavras.
a leitura sem repeticoes estava demorando mais de 5 minutos.*/

palavra** discard(palavra** original, int* contadorVelho, int* contadorNovo, int tamanhoMaximo){
    int i, j, k;
    int tamanhoTemp;
    int *tamanhoAtual; //espaco alocado para o vetor de palavras matriz[i];
    palavra** matriz;

    matriz = (palavra**) malloc(tamanhoMaximo * sizeof (palavra*)); //aloca a nova matriz de palavras (sem repeticoes)
    check(matriz, "Erro ao alocar matriz de palavras(4).\n");

    for(i = 0; i < tamanhoMaximo; i++){ //inicializa cada vetor de palavras apontando pra NULL
        matriz[i] = NULL;
        contadorNovo[i] = 0;
    }

    tamanhoAtual = (int*) calloc(tamanhoMaximo, sizeof(int));

    for(i = 0; i < tamanhoMaximo; i++){
        for(j = 0; j < contadorVelho[i]; j++){ //percorre todas as palavras da matriz velha
            tamanhoTemp = strlen(original[i][j].string);
            if(j == 0 || strcmp(original[i][j].string, original[i][j-1].string)){ //se a palavra for a primeira do vetor ou se for diferente da anterior
                if(contadorNovo[tamanhoTemp] >= tamanhoAtual[tamanhoTemp]){ //se nao cabe mais palavras de tamanho tamanhoTemp no vetor de palavras deste tamanho.
                    tamanhoAtual[tamanhoTemp] += INC;
                    matriz[tamanhoTemp] = realloc(matriz[tamanhoTemp], tamanhoAtual[tamanhoTemp] * sizeof(palavra)); //aloca espaco para mais 100 palavras de tamanho tamanhoTemp.
                    check(matriz[tamanhoTemp], "Erro ao alocar matriz de palavras(2).\n");
                    for(k = tamanhoAtual[tamanhoTemp] - INC; k < tamanhoAtual[tamanhoTemp]; k++){ //aloca espaco para as palavras de fato.
                        matriz[tamanhoTemp][k].string = (char*) malloc ((tamanhoTemp+1) * sizeof(char)); //aloca espaco para as palavras + o \0
                        check(matriz[tamanhoTemp][k].string, "Erro ao alocar matriz de palavras(3).\n");
                    }
                }
                strcpy(matriz[tamanhoTemp][contadorNovo[i]].string, original[i][j].string); /*copia*/
                matriz[tamanhoTemp][contadorNovo[i]].found = 0; /*reseta flag de nao encontrado*/
                contadorNovo[tamanhoTemp]++; /*incrementa contador de palavras deste tamanho*/
            }
        }
    }
    free(tamanhoAtual);
    return matriz;
}

char* fileToBuffer(char* filename){  //retorna um ponteiro pro começo da string que contem o texto do arquivo
    long size;
    FILE *f = fopen(filename, "rb"); /*abre arquivo em modo binario*/
    char *temp, *aux;

    check(f, "Erro ao abrir arquivo.");

    fseek(f, 0, SEEK_END); /*posiciona ponteiro no final para determinar o tamanho do arquivo*/
    size = ftell(f);       /*determina o tamanho do arquivo*/
    fseek(f, 0, SEEK_SET); /*volta o ponteiro para o comeco*/

    temp = (char*) malloc((size+1) * sizeof(char)); /*aloca uma string do tamanho do arquivo + 1 (para o '\0') */
    check(temp, "Memoria insuficiente.\n");

    fread(temp, sizeof(char), size, f); /*le o arquivo para a string*/
    temp[size] = '\0'; /*coloca o '\0' no final*/
    aux = temp;        /*pre-processa a string tirando caracteres indesejados. só restarao letras convertidas para minusculo, espacos e '-'*/
    while(*aux != '\0'){
        if(*aux >= 'A' && *aux <= 'Z')
            *aux += 32;
        if(*aux != '-' &&(*aux < 'a' || *aux > 'z'))
            *aux = ',';
        aux++;
    }
    fclose(f); /*fecha arquivo*/
    return temp; /*retorna a string*/
}

char* dividePalavras(palavra** matriz, int altura, int* larguras){
    int i, j, k = 0, pos;
    int currentSize = 0;
    char* ptr;
    char* buffer = malloc(sizeof(char));
    currentSize++;

    for(i = 6; i < altura; i++){
        currentSize += larguras[i] * (sizeof(char) * (i+1) + i / 5);
        buffer = (char*) realloc (buffer, currentSize); //aloca espaco suficente para conter uma linha da matriz, sem as flags
        check(buffer, "Erro ao alocar buffer (1)");
        for(j = 0; j < larguras[i]; j++){
            ptr = matriz[i][j].string;
            pos = 0;
            buffer[k] = ',';
            k++;
            while(*ptr){
                buffer[k] = *ptr;
                ptr++;
                pos++;
                k++;
                if(pos == 5){
                    buffer[k] = ',';
                    pos = 0;
                    k++;
                }
            }
        }
    }
    buffer[k] = '\0';
    return buffer;
}

void imprimeMatriz(palavra** matriz, int altura, int* larguras){
    int i, j;
    for(i = 1; i < altura; i++){
        for(j = 0; j < larguras[i]; j++)
            printf("%s ", matriz[i][j].string);
        printf("\n\n");
    }
}

void limpaMatriz(palavra** matriz, int altura, int* larguras){
    int i, j;
    for(i = 0; i < altura; i++){
        for(j = 0; j < larguras[i]; j++)
            free(matriz[i][j].string);
        free(matriz[i]);
    }
    free(matriz);
}

void randomizeWord(char* word, int size){  //cria palavras aleatoriamente

    char *aux;
    int i = 0, num = 0;

    aux = word;
    while(i < size){ //size eh o tamanho da palavra que queremos gerar
         num = (97 + rand() % 27); //gera numeros entre 0 e 26 inclusos. se for 26 troca por hifen (-)
         if(num == 123)
            num = 45;
         *aux = (char)num; //converte pra char
         aux++;
         i++;
    }
    *aux = '\0';
}
